<html>
<head>
	<meta charset="UTF-8">
	<meta content="IE=edge" http-equiv="X-UA-Compatible">
	<meta content="initial-scale=1.0, maximum-scale=1.0, user-scalable=no, width=device-width" name="viewport">
	<title>3891：[Usaco2014 Dec]Piggy Back</title>
	<!-- css -->
	<link href="../css/base.min.css" rel="stylesheet">
	<link href="../css/project.min.css" rel="stylesheet">
	
	<!-- favicon -->
	<!-- ... -->
</head>
<body class="page-brand">
	<header class="header header-transparent header-waterfall ui-header">
		<ul class="nav nav-list pull-left">
			<li>
				<a data-toggle="menu" href="#menu">
					<span class="icon icon-lg">menu</span>
				</a>
			</li>
		</ul>
		<a class="header-logo header-affix-hide margin-left-no margin-right-no" data-offset-top="213" data-spy="affix">[Usaco2014 Dec]Piggy Back</a>
		<span class="header-logo header-affix margin-left-no margin-right-no" data-offset-top="213" data-spy="affix">[Usaco2014 Dec]Piggy Back</span>
	</header>
	<nav aria-hidden="true" class="menu" id="menu" tabindex="-1">
		<div class="menu-scroll">
			<div class="menu-content">
				<a class="menu-logo" href="../index.html">BZOJ离线题库</a>
				<ul class="nav">
					<li>
						<a class="waves-attach" data-toggle="collapse" href="#problems">题目</a>
						<ul class="menu-collapse collapse in" id="problems">
							<li>
								<a class="waves-attach" href="../index.html">主页</a>
							</li>
							<li>
								<a class="waves-attach" href="../list.html">题目列表</a>
							</li>
						</ul>
					</li>
					<li>
						<a class="collapsed waves-attach" data-toggle="collapse" href="#about">关于</a>
						<ul class="menu-collapse collapse" id="about">
							<li>
								<a class="waves-attach" href="../about.html">关于此项目</a>
							</li>
						</ul>
					</li>
					
				</ul>
			</div>
		</div>
	</nav>
	<main class="content">
		<div class="content-header ui-content-header">
			<div class="container">
				<h1 class="content-heading">
                [Usaco2014 Dec]Piggy Back                </h1>
                <p>时间限制：10s&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;  空间限制：128MB</p>			</div>
		</div>
		<div class="container">
			<section class="content-inner margin-top-no">
				<div class="row">
					<div class="col-lg-13 col-md-13">
						<div class="card margin-bottom-no">
							<div class="card-main">
								<div class="card-inner">
									
                                <h3>题目描述</h3><p><p><span style="font-family: monospace; font-size: 14px; white-space: pre-wrap;">Bessie and her sister Elsie graze in different fields during the day, and in the evening they both want to walk back to the barn to rest. Being clever bovines, they come up with a plan to minimize the total amount of energy they both spend while walking.  Bessie spends B units of energy when walking from a field to an adjacent field, and Elsie spends E units of energy when she walks to an adjacent field.  However, if Bessie and Elsie are together in the same field, Bessie can carry Elsie on her shoulders and both can move to an adjacent field while spending only P units of energy (where P might be considerably less than B+E, the amount Bessie and Elsie would have spent individually walking to the adjacent field).  If P is very small, the most energy-efficient solution may involve Bessie and Elsie traveling to a common meeting field, then traveling together piggyback for the rest of the journey to the barn.  Of course, if P is large, it may still make the most sense for Bessie and Elsie to travel separately.  On a side note, Bessie and Elsie are both unhappy with the term &quot;piggyback&quot;, as they don't see why the pigs on the farm should deserve all the credit for this remarkable form of transportation.  Given B, E, and P, as well as the layout of the farm, please compute the minimum amount of energy required for Bessie and Elsie to reach the barn.<br />
</span></p>
<div>给定一个N个点M条边的无向图，其中Bessie在1号点，Elsie在2号点，它们的目的地为N号点。Bessie每经过一条边需要消耗B点能量，Elsie每经过一条边需要消耗E点能量。当它们相遇时，它们可以一起行走，此时它们每经过一条边需要消耗P点能量。求它们两个到达N号点时最少消耗多少能量？</div>
<p><span style="font-family: monospace; font-size: 14px; white-space: pre-wrap;"> </span></p>
<p></p>
<p></p></p><hr/><h3>输入格式</h3><p><div><span style="font-family: monospace; font-size: 14px; white-space: pre-wrap;">The first line of input contains the positive integers B, E, P, N, and M.  All of these are at most 40,000.  B, E, and P are described above. N is the number of fields in the farm (numbered 1..N, where N &gt;= 3), and M is the number of connections between fields.  Bessie and Elsie start in fields 1 and 2, respectively.  The barn resides in field N.  The next M lines in the input each describe a connection between a pair of different fields, specified by the integer indices of the two fields.  Connections are bi-directional.  It is always possible to travel from field 1 to field N, and field 2 to field N, along a series of such connections.  <br />
</span></div>
<p></p></p><hr/><h3>输出格式</h3><p><div>A single integer specifying the minimum amount of energy Bessie and</div>
<div>Elsie collectively need to spend to reach the barn. &nbsp;In the example</div>
<div>shown here, Bessie travels from 1 to 4 and Elsie travels from 2 to 3</div>
<div>to 4. &nbsp;Then, they travel together from 4 to 7 to 8.</div>
<div></div>
<p></p></p><hr/><h3>样例输入</h3><pre>4 4 5 8 8
1 4
2 3
3 4
4 7
2 5
5 6
6 8
7 8</pre><hr/><h3>样例输出</h3><pre>22</pre><hr/><h3>提示</h3><p>没有写明提示</p><hr/><h3>题目来源</h3><p>Silver</p>
								</div>
							</div>
						</div>
					</div>
				</div>
				
				
			</section>
		</div>
	</main>

	<div class="fbtn-container">
		<div class="fbtn-inner">
			<a class="fbtn fbtn-lg fbtn-brand-accent waves-attach waves-circle waves-light waves-effect" data-toggle="dropdown" aria-expanded="true"><span class="fbtn-text fbtn-text-left">Menu</span><span class="fbtn-ori icon">apps</span><span class="fbtn-sub icon">close</span></a>
			<div class="fbtn-dropup">
				<a class="fbtn fbtn-brand waves-attach waves-circle waves-light waves-effect" href="../list.html" target="_self"><span class="fbtn-text fbtn-text-left">题目列表</span><span class="icon">menu</span></a>
				<a class="fbtn fbtn-green waves-attach waves-circle waves-effect" href="../index.html" target="_self"><span class="fbtn-text fbtn-text-left">返回主页</span><span class="icon">home</span></a>
				<a class="fbtn waves-attach waves-circle waves-effect" href="http://www.lydsy.com/JudgeOnline/submitpage.php?id=3891" target="_blank"><span class="fbtn-text fbtn-text-left">提交代码</span><span class="icon">send</span></a>
				<a class="fbtn fbtn-orange waves-attach waves-circle waves-effect" href="http://www.lydsy.com/JudgeOnline/wttl/wttl.php?pid=3891" target="_blank"><span class="fbtn-text fbtn-text-left">试题讨论</span><span class="icon">chat</span></a>
				
			</div>
		</div>
	</div>

	<!-- js -->
	<script src="../js/jquery.min.js"></script>
	<script src="../js/base.min.js"></script>
	<script src="../js/project.min.js"></script>
</body>
</html>